//Given the root of a binary search tree, return a balanced binary search tree 
//with the same node values. If there is more than one answer, return any of them. 
//
//
// A binary search tree is balanced if the depth of the two subtrees of every 
//node never differs by more than 1. 
//
// 
// Example 1: 
//
// 
//Input: root = [1,null,2,null,3,null,4,null,null]
//Output: [2,1,3,null,null,null,4]
//Explanation: This is not the only correct answer, [3,1,4,null,2] is also 
//correct.
// 
//
// Example 2: 
//
// 
//Input: root = [2,1,3]
//Output: [2,1,3]
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the tree is in the range [1, 10⁴]. 
// 1 <= Node.val <= 10⁵ 
// 
// Related Topics 贪心 树 深度优先搜索 二叉搜索树 分治 二叉树 👍 88 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //思路：中序遍历得到有序数组（结点），然后通过找中点递归建树
    public  TreeNode balanceBST(TreeNode root) {
        //得到一个有序数组
        Integer[] orderArray = inOrderTraverse(root);
        //通过找中点的方法递归建树
        TreeNode BST = initBinarySearchTree(orderArray,0,orderArray.length-1);
        return BST;
    }

    public  Integer[] inOrderTraverse(TreeNode root){
        //频繁插入元素的场景，LinkedList性能比ArrayList更高
        LinkedList<Integer> list = new LinkedList<>();
        //将LinkedList转换成普通的数组
        LinkedList<Integer> resultList = inOrderAppend(root, list);
        return resultList.toArray(new Integer[resultList.size()]);
    }

    /*
        有序数组构建成二叉搜索树
        区别于上面的普通构建二叉树的方法，这个方法可以快捷构建二叉搜索树。
        上面的方法入参数组可以是无序的，但是这个方法是有序 -->  构建二叉搜索树
        思想是找中点，递归构建
     */
    //找 start和 end 要么都找下标（比如0和arr.length-1）,要么就都找实际位置（比如1和arr.length）
    public  TreeNode initBinarySearchTree(Integer[] arr, int start, int end) {
        if (start > end){
            return null;
        }
        int mid = (start+end)/2;

        TreeNode treeNode = new TreeNode(arr[mid], null, null);     //在中点创建一个结点作为根节点
        treeNode.left = initBinarySearchTree(arr,start,mid-1);
        treeNode.right = initBinarySearchTree(arr,mid+1,end);

        return treeNode;
    }
    private LinkedList<Integer> inOrderAppend(TreeNode root, LinkedList<Integer> list){
        if (root == null){  //边界检查
            return null;
        }
        if (root.left!=null){
            inOrderAppend(root.left,list);
        }
        list.add(root.val);
        if (root.right!=null){
            inOrderAppend(root.right,list);
        }
        return list;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
